package 热题100;

import java.util.ArrayList;

public class 热题3最长无重复字串 {

    public static void main(String[] args) {
        int len = lengthOfLongestSubstring("abac");
        System.out.println(len);
    }

    /**
     * 传入一个字串，计算最长连续字串
     * @param s
     * @return
     */
    //使用滑动窗口，来计算最长无重复字串
    public static int lengthOfLongestSubstring(String s) {
       int left = 0;
       int right = 0;
        char[] ch = s.toCharArray();
        int maxLen = 0;
        ArrayList<Character> list = new ArrayList<>();
        while (left < ch.length && right < ch.length){
            //将所有的不重复的添加进去
            while (right < ch.length && !list.contains(ch[right])){
                list.add(ch[right]);
                right++;
            }

            //出现重复,计算最长字串
            maxLen = maxLen > right - left ? maxLen : right - left;
            //如果此时right已经越界，只需要判断最大长度和list的大小，然后直接退出
            if (right == ch.length){
                return maxLen > list.size() ? maxLen : list.size();
            }

            //否则还需要继续处理，消除重复的字符。
            int i = 0;
            while (left < right ){
                if (ch[left] != ch[right]){
                    left++;
                    list.remove(i);
                }else {
                    list.remove(i);
                    left++;
                    break;
                }
            }
        }
        //最后right达到了终点，返回即可。
        return maxLen;
    }

}
